#include <bits/stdc++.h>

using namespace std;

// class Solution // NlogN
// {
// public:
//     int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
//     {
//         int ans = 0, n = fruits.size();
//         vector<int> prefixSum(n + 1, 0);
//         for (int i = 0; i < n; ++i)
//         {
//             prefixSum[i + 1] = prefixSum[i] + fruits[i][1];
//             cout << prefixSum[i + 1] << " ";
//         }
//         cout << endl;
//         int limitR = startPos + k, limitL = startPos - k;
//         auto right_it = upper_bound(
//             fruits.begin(), fruits.end(), limitR, [](int v, const vector<int> &x)
//             { return v < x[0]; });
//         int right = distance(fruits.begin(), right_it) - 1;
//         if (right < 0)
//         {
//             return 0;
//         }
//         cout << right << " " << endl;
//         for (; right >= 0 && fruits[right][0] >= startPos; --right)
//         {
//             int cost = fruits[right][0] - startPos;
//             int leftD = max((k - cost) / 2, k - 2 * cost);
//             auto left_it = lower_bound(
//                 fruits.begin(), fruits.end(), startPos - leftD, [](const vector<int> &x, int v)
//                 { return v > x[0]; });
//             int left = distance(fruits.begin(), left_it);
//             cout << left << " " << right << " " << endl;
//             ans = max(ans, prefixSum[right + 1] - prefixSum[left]);
//         }
//         int left = lower_bound(
//                        fruits.begin(), fruits.end(), limitL, [](const vector<int> &x, int v)
//                        { return v > x[0]; }) -
//                    fruits.begin();
//         int start = upper_bound(fruits.begin(), fruits.end(), startPos, [](int v, const vector<int> &x)
//                                 { return v < x[0]; }) -
//                     fruits.begin();
//         ans = max(ans, prefixSum[start] - prefixSum[left]);
//         cout << endl;
//         return ans;
//     }
// };

class Solution // N
{
public:
    int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
    {
        int left = lower_bound(fruits.begin(), fruits.end(), startPos - k, [](const auto &a, int b)
                               { return a[0] < b; }) -
                   fruits.begin(); // 向左最远能到 fruits[left][0]
        int right = left, s = 0, n = fruits.size();
        for (; right < n && fruits[right][0] <= startPos; ++right)
            s += fruits[right][1]; // 从 fruits[left][0] 到 startPos 的水果数
        int ans = s;
        for (; right < n && fruits[right][0] <= startPos + k; ++right)
        {
            s += fruits[right][1]; // 枚举最右位置为 fruits[right][0]
            while (fruits[right][0] * 2 - fruits[left][0] - startPos > k &&
                   fruits[right][0] - fruits[left][0] * 2 + startPos > k)
                s -= fruits[left++][1]; // fruits[left][0] 无法到达
            ans = max(ans, s);          // 更新答案最大值
        }
        return ans;
    }
};

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solutions/2254860/hua-dong-chuang-kou-jian-ji-xie-fa-pytho-1c2d/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

int main()
{

    // system("pause");
    return 0;
}
